﻿package list;

import java.util.Stack;

import common.Node;

public class 从链表中删除指定值的元素 {
	// 利用栈或者其他容器，将不等于value的节点收集起来，收集完成后重新连接
	public static Node removeByValue1(Node head, int value) {
		if (head == null)
			return null;
		Stack<Node> stack = new Stack<>();
		while (head != null) {
			if (head.value != value) {
				stack.push(head);
			}
			head = head.next;
		}
		while (!stack.isEmpty()) {
			stack.peek().next = head;
			head = stack.pop();
		}
		return head;
	}

	// 方法2：不利用任何容器而直接进行调整，时间复杂度为o(1),额外空间复杂度为o(1)
	public static Node removeByValue2(Node head, int value) {
		// 找到第一个不是value的节点
		while (head != null) {
			if (head.value != value) {
				break;
			}
			head = head.next;
		}

		// 继续寻找那些元素值是value的节点

		Node pre = head;
		Node cur = head;
		while (cur != null) {
			if (cur.value == value) {
				pre.next = cur.next;
			} else {
				pre = cur;
			}
			cur = cur.next;
		}
		return head;
	}
}
